class Solution {
public:
    int f[32][2] = {0};  
    
    int getLen(int x){
        for(int i = 31;i >= 0;i--){
            if(((x >> i) & 1) == 1) return i+1;
        }
        return 0;
    }
    int dp(int x){
        int len = getLen(x);
     
        int ans = 0;
        int cur = 0,prev = 0;
        for(int i = len-1;i >= 0;i--){
            cur = (x >> i) & 1;
            if(cur == 1){
                ans += f[i+1][0];
            }
            if(cur == 1 && prev == 1) break;
            prev = cur;
                                                                                   if(i == 0) ans++;
        }
        return ans;
    }              
                                        
    int findIntegers(int n) {
        f[1][0] = 1;
        f[1][1] = 1;
        for(int i = 2;i < 32;i++){
            f[i][0] = f[i-1][0] + f[i-1][1];
            f[i][1] = f[i-1][0];
        }
    
        return dp(n);
    }
};
